use crate::src::struct_and_type::{Trie, TrieNode, TrieValue};
use :: libc;
extern "C" {
    fn malloc(_: u64) -> *mut libc::c_void;
    fn calloc(_: u64, _: u64) -> *mut libc::c_void;
    fn free(_: *mut libc::c_void);
}
#[no_mangle]
pub extern "C" fn trie_new() -> *mut Trie {
    let mut new_trie: *mut Trie = 0 as *mut Trie;
    new_trie = (unsafe { malloc(::core::mem::size_of::<Trie>() as u64) }) as *mut Trie;
    if new_trie.is_null() {
        return 0 as *mut Trie;
    }
    (unsafe { (*new_trie).root_node = 0 as *mut TrieNode });
    return new_trie;
}
extern "C" fn trie_free_list_push(mut list: *mut *mut TrieNode, mut node: *mut TrieNode) {
    (unsafe { (*node).data = *list as TrieValue });
    (unsafe { *list = node });
}
extern "C" fn trie_free_list_pop(mut list: *mut *mut TrieNode) -> *mut TrieNode {
    let mut result: *mut TrieNode = 0 as *mut TrieNode;
    result = unsafe { *list };
    (unsafe { *list = (*result).data as *mut TrieNode });
    return result;
}
#[no_mangle]
pub extern "C" fn trie_free(mut trie: *mut Trie) {
    let mut free_list: *mut TrieNode = 0 as *mut TrieNode;
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut i: i32 = 0;
    free_list = 0 as *mut TrieNode;
    if !(unsafe { (*trie).root_node }).is_null() {
        trie_free_list_push(&mut free_list, unsafe { (*trie).root_node });
    }
    while !free_list.is_null() {
        node = trie_free_list_pop(&mut free_list);
        i = 0 as i32;
        while i < 256 as i32 {
            if !(unsafe { (*node).next[i as usize] }).is_null() {
                trie_free_list_push(&mut free_list, unsafe { (*node).next[i as usize] });
            }
            i += 1;
            i;
        }
        (unsafe { free(node as *mut libc::c_void) });
    }
    (unsafe { free(trie as *mut libc::c_void) });
}
extern "C" fn trie_find_end(mut trie: *mut Trie, mut key: *mut i8) -> *mut TrieNode {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut p: *mut i8 = 0 as *mut i8;
    node = unsafe { (*trie).root_node };
    p = key;
    while (unsafe { *p }) as i32 != '\0' as i32 {
        if node.is_null() {
            return 0 as *mut TrieNode;
        }
        node = unsafe { (*node).next[*p as u8 as usize] };
        p = unsafe { p.offset(1) };
        p;
    }
    return node;
}
extern "C" fn trie_find_end_binary(
    mut trie: *mut Trie,
    mut key: *mut u8,
    mut key_length: i32,
) -> *mut TrieNode {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut j: i32 = 0;
    let mut c: i32 = 0;
    node = unsafe { (*trie).root_node };
    j = 0 as i32;
    while j < key_length {
        if node.is_null() {
            return 0 as *mut TrieNode;
        }
        c = (unsafe { *key.offset(j as isize) }) as i32;
        node = unsafe { (*node).next[c as usize] };
        j += 1;
        j;
    }
    return node;
}
extern "C" fn trie_insert_rollback(mut trie: *mut Trie, mut key: *mut u8) {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut prev_ptr: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut next_node: *mut TrieNode = 0 as *mut TrieNode;
    let mut next_prev_ptr: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut p: *mut u8 = 0 as *mut u8;
    node = unsafe { (*trie).root_node };
    prev_ptr = unsafe { &mut (*trie).root_node };
    p = key;
    while !node.is_null() {
        next_prev_ptr = (unsafe { &mut *((*node).next).as_mut_ptr().offset(*p as isize) })
            as *mut *mut TrieNode;
        next_node = unsafe { *next_prev_ptr };
        p = unsafe { p.offset(1) };
        p;
        (unsafe { (*node).use_count = ((*node).use_count).wrapping_sub(1) });
        (unsafe { (*node).use_count });
        if (unsafe { (*node).use_count }) == 0 as i32 as u32 {
            (unsafe { free(node as *mut libc::c_void) });
            if !prev_ptr.is_null() {
                (unsafe { *prev_ptr = 0 as *mut TrieNode });
            }
            next_prev_ptr = 0 as *mut *mut TrieNode;
        }
        node = next_node;
        prev_ptr = next_prev_ptr;
    }
}
#[no_mangle]
pub extern "C" fn trie_insert(mut trie: *mut Trie, mut key: *mut i8, mut value: TrieValue) -> i32 {
    let mut rover: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut p: *mut i8 = 0 as *mut i8;
    let mut c: i32 = 0;
    if value.is_null() {
        return 0 as i32;
    }
    node = trie_find_end(trie, key);
    if !node.is_null() && !(unsafe { (*node).data }).is_null() {
        (unsafe { (*node).data = value });
        return 1 as i32;
    }
    rover = unsafe { &mut (*trie).root_node };
    p = key;
    loop {
        node = unsafe { *rover };
        if node.is_null() {
            node = (unsafe { calloc(1 as i32 as u64, ::core::mem::size_of::<TrieNode>() as u64) })
                as *mut TrieNode;
            if node.is_null() {
                trie_insert_rollback(trie, key as *mut u8);
                return 0 as i32;
            }
            (unsafe { (*node).data = 0 as *mut libc::c_void });
            (unsafe { *rover = node });
        }
        (unsafe { (*node).use_count = ((*node).use_count).wrapping_add(1) });
        (unsafe { (*node).use_count });
        c = (unsafe { *p }) as u8 as i32;
        if c == '\0' as i32 {
            (unsafe { (*node).data = value });
            break;
        } else {
            rover = (unsafe { &mut *((*node).next).as_mut_ptr().offset(c as isize) })
                as *mut *mut TrieNode;
            p = unsafe { p.offset(1) };
            p;
        }
    }
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn trie_insert_binary(
    mut trie: *mut Trie,
    mut key: *mut u8,
    mut key_length: i32,
    mut value: TrieValue,
) -> i32 {
    let mut rover: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut p: i32 = 0;
    let mut c: i32 = 0;
    if value.is_null() {
        return 0 as i32;
    }
    node = trie_find_end_binary(trie, key, key_length);
    if !node.is_null() && !(unsafe { (*node).data }).is_null() {
        (unsafe { (*node).data = value });
        return 1 as i32;
    }
    rover = unsafe { &mut (*trie).root_node };
    p = 0 as i32;
    loop {
        node = unsafe { *rover };
        if node.is_null() {
            node = (unsafe { calloc(1 as i32 as u64, ::core::mem::size_of::<TrieNode>() as u64) })
                as *mut TrieNode;
            if node.is_null() {
                trie_insert_rollback(trie, key);
                return 0 as i32;
            }
            (unsafe { (*node).data = 0 as *mut libc::c_void });
            (unsafe { *rover = node });
        }
        (unsafe { (*node).use_count = ((*node).use_count).wrapping_add(1) });
        (unsafe { (*node).use_count });
        c = (unsafe { *key.offset(p as isize) }) as i32;
        if p == key_length {
            (unsafe { (*node).data = value });
            break;
        } else {
            rover = (unsafe { &mut *((*node).next).as_mut_ptr().offset(c as isize) })
                as *mut *mut TrieNode;
            p += 1;
            p;
        }
    }
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn trie_remove_binary(
    mut trie: *mut Trie,
    mut key: *mut u8,
    mut key_length: i32,
) -> i32 {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut next: *mut TrieNode = 0 as *mut TrieNode;
    let mut last_next_ptr: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut p: i32 = 0;
    let mut c: i32 = 0;
    node = trie_find_end_binary(trie, key, key_length);
    if !node.is_null() && !(unsafe { (*node).data }).is_null() {
        (unsafe { (*node).data = 0 as *mut libc::c_void });
    } else {
        return 0 as i32;
    }
    node = unsafe { (*trie).root_node };
    last_next_ptr = unsafe { &mut (*trie).root_node };
    p = 0 as i32;
    loop {
        c = (unsafe { *key.offset(p as isize) }) as i32;
        next = unsafe { (*node).next[c as usize] };
        (unsafe { (*node).use_count = ((*node).use_count).wrapping_sub(1) });
        (unsafe { (*node).use_count });
        if (unsafe { (*node).use_count }) <= 0 as i32 as u32 {
            (unsafe { free(node as *mut libc::c_void) });
            if !last_next_ptr.is_null() {
                (unsafe { *last_next_ptr = 0 as *mut TrieNode });
                last_next_ptr = 0 as *mut *mut TrieNode;
            }
        }
        if p == key_length {
            break;
        }
        p += 1;
        p;
        if !last_next_ptr.is_null() {
            last_next_ptr = (unsafe { &mut *((*node).next).as_mut_ptr().offset(c as isize) })
                as *mut *mut TrieNode;
        }
        node = next;
    }
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn trie_remove(mut trie: *mut Trie, mut key: *mut i8) -> i32 {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    let mut next: *mut TrieNode = 0 as *mut TrieNode;
    let mut last_next_ptr: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut p: *mut i8 = 0 as *mut i8;
    let mut c: i32 = 0;
    node = trie_find_end(trie, key);
    if !node.is_null() && !(unsafe { (*node).data }).is_null() {
        (unsafe { (*node).data = 0 as *mut libc::c_void });
    } else {
        return 0 as i32;
    }
    node = unsafe { (*trie).root_node };
    last_next_ptr = unsafe { &mut (*trie).root_node };
    p = key;
    loop {
        c = (unsafe { *p }) as u8 as i32;
        next = unsafe { (*node).next[c as usize] };
        (unsafe { (*node).use_count = ((*node).use_count).wrapping_sub(1) });
        (unsafe { (*node).use_count });
        if (unsafe { (*node).use_count }) <= 0 as i32 as u32 {
            (unsafe { free(node as *mut libc::c_void) });
            if !last_next_ptr.is_null() {
                (unsafe { *last_next_ptr = 0 as *mut TrieNode });
                last_next_ptr = 0 as *mut *mut TrieNode;
            }
        }
        if c == '\0' as i32 {
            break;
        }
        p = unsafe { p.offset(1) };
        p;
        if !last_next_ptr.is_null() {
            last_next_ptr = (unsafe { &mut *((*node).next).as_mut_ptr().offset(c as isize) })
                as *mut *mut TrieNode;
        }
        node = next;
    }
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn trie_lookup(mut trie: *mut Trie, mut key: *mut i8) -> TrieValue {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    node = trie_find_end(trie, key);
    if !node.is_null() {
        return unsafe { (*node).data };
    } else {
        return 0 as *mut libc::c_void;
    };
}
#[no_mangle]
pub extern "C" fn trie_lookup_binary(
    mut trie: *mut Trie,
    mut key: *mut u8,
    mut key_length: i32,
) -> TrieValue {
    let mut node: *mut TrieNode = 0 as *mut TrieNode;
    node = trie_find_end_binary(trie, key, key_length);
    if !node.is_null() {
        return unsafe { (*node).data };
    } else {
        return 0 as *mut libc::c_void;
    };
}
#[no_mangle]
pub extern "C" fn trie_num_entries(mut trie: *mut Trie) -> u32 {
    if (unsafe { (*trie).root_node }).is_null() {
        return 0 as i32 as u32;
    } else {
        return unsafe { (*(*trie).root_node).use_count };
    };
}
